package practise.alogrithm.hundredInterviewQuestions;

import java.util.ArrayList;
import java.util.List;

/**
 * from a ordered array, get all subset index,  whose sum equal to the input number.
 */
public class AllSubsetOfSum {
    public static List<List<Integer>> getAllSubsetOfSum(int[] arrays, int sum){
        int startPointer =0;
        int endPointer=0;
        List<List<Integer>> result = new ArrayList<>();
        for(;arrays[startPointer]<=(sum/2);startPointer++){
            int innerSum=0;
            endPointer=startPointer;
            for(;innerSum<sum;endPointer++){
                if((innerSum+=arrays[endPointer])==sum){
                    List<Integer> numbers = new ArrayList<>();
                    numbers.add(startPointer);
                    numbers.add(endPointer);
                    result.add(numbers);
                    break;
                }

            }
        }
        return result;
    }

    public static void main(String[] args){
        System.out.print("result:"+getAllSubsetOfSum(new int[]{1,2,3,4,5,6,7,8},15));
    }
}
